package com.csx.heap;

import com.csx.array.Array;

import java.util.Random;

/**
 * 最大堆
 * @param <E> 可比较的类型
 */
public class MaxHeap<E extends Comparable<E>>  {

    private Array<E> data;

    public MaxHeap(int capacity){
        data = new Array<>(capacity);
    }

    public MaxHeap(){
        data = new Array<>();
    }

    /**
     *  数组转最大堆
     * @param arr 数组
     * @throws IllegalAccessException 异常
     */
    public MaxHeap(E[] arr) throws IllegalAccessException {

        data = new Array<E>(arr);
        for (int i = parent(arr.length - 1); i >= 0 ; i--) {
            siftDown(i);
        }
    }

    /**
     * 返回堆中的元素个数
     * @return 个数
     */
    public int size(){
        return data.getSize();
    }

    /**
     * 返回一个布尔值,表示堆中是否为空
     * @return true 为空 false 不为空
     */
    public boolean isEmpty(){
        return data.isEmpty();
    }

    /**
     * 返回完全二叉树的数组对应的,一个索引所表示的元素的父亲节点的索引
     * @param index 索引
     * @return 父亲节点索引
     */
    private int parent(int index) throws IllegalAccessException {
        if (index == 0){
            throw new IllegalAccessException("index 为0 ,他没有父亲节点");
        }
        return (index - 1) / 2;
    }

    /**
     * 返回完全二叉树的数组对应的,一个索引所表示的元素的左孩子节点的索引
     * @param index 索引
     * @return 左孩子节点的索引
     */
    private int leftChild(int index){
        return index * 2 + 1 ;
    }

    /**
     * 返回完全二叉树的数组对应的,一个索引所表示的元素的右孩子节点的索引
     * @param index 索引
     * @return 右孩子节点的索引
     */
    private int rightChild(int index){
        return index * 2 + 2 ;
    }

    /**
     * 向堆中添加元素
     */
    public void add(E e) throws IllegalAccessException {
        data.addLast(e);
        siftUp(data.getSize() - 1);
    }

    /**
     * 上浮
     * @param k  size值
     * @throws IllegalAccessException
     */
    private void siftUp(int k) throws IllegalAccessException {
        while(k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0){
            data.swap(k,parent(k));
        }
    }

    /**
     * 下沉
     * @param k 最大元素下标
     */
    private void siftDown(int k) throws IllegalAccessException {
        while(leftChild(k) < data.getSize()){
            int j = leftChild(k);
            if (j + 1 < data.getSize() && data.get(j + 1).compareTo(data.get(j)) > 0){
                j = rightChild(k);
            }
            if (data.get(k).compareTo(data.get(j)) >= 0){
                break;
            }
            data.swap(k, j);
            k = j;
        }
    }

    /**
     * 取出堆中最大的元素
     * @return 最大的元素
     */
    public E extractMax() throws IllegalAccessException {
        E ret = findMax();

        data.swap(0,data.getSize() - 1);
        data.deleteLast();
        siftDown(0);
        return ret;
    }



    /**
     * 查看堆中最大的元素
     * @return 最大的元素
     * @throws IllegalAccessException 非法异常
     */
    public E findMax() throws IllegalAccessException {
        if (data.getSize() == 0){
            throw new IllegalAccessException("Can not findMax when heap is empty");
        }
        return data.get(0);
    }

    public E replace(E e) throws IllegalAccessException {
        E ret = findMax();
        data.set(0, e);
        siftDown(0);
        return ret;
    }



    public static void main(String[] args) throws IllegalAccessException {

        Random random = new Random();
        Integer[] arr = new Integer[5000000];
        for (int i = 0; i <  5000000; i++) {
            arr[i] = random.nextInt(Integer.MAX_VALUE);
        }


        long starTime = System.nanoTime();

        MaxHeap<Integer> maxHeap = new MaxHeap<>(arr);

        long endTime = System.nanoTime();
        double v = (endTime - starTime) / 1000000000.0;

        System.out.println(v);

        long starTime1 = System.nanoTime();

        MaxHeap<Integer> maxHeap1 = new MaxHeap<>();
        for (int num : arr){
            maxHeap.add(num);
        }

        long endTime1 = System.nanoTime();
        double v1 = (endTime1 - starTime1) / 1000000000.0;

        System.out.println(v1);
    }
}
